package eleven;

import java.util.Arrays;

/**
 * 53. 最大子数组和
 */
public class Day20 {
    public int maxSubArray(int[] nums) {//时间复杂度还是太大了 后续要用动态规划 前缀和求解
        int maxValue = Arrays.stream(nums).max().getAsInt();
        if (maxValue <= 0) return maxValue;
        int n = nums.length,ans = 0, maxSum = 0;
        for (int i = 0; i < n; i++) {
            ans += nums[i];
            if (ans < 0) ans = 0;
            else maxSum = Math.max(maxSum,ans);
        }
        return maxSum;
    }
    public static void main(String[] args) {
        int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
        Day20 day20 = new Day20();
        System.out.println(day20.maxSubArray(arr));
    }
}

/*
    public int maxSubArray(int[] nums) {//时间复杂度大
        int maxValue = Arrays.stream(nums).max().getAsInt();
        if (maxValue <= 0) return maxValue;
        int i = 0,j = 0,ans = 0, maxSum = 0,n = nums.length;
        while (i < n && j < n){
            while (i < n && nums[i] < 0) i++;
            j = i;
            while (i < n && j < n){
                if (ans + nums[j] > 0){
                    ans += nums[j];
                    j++;
                    maxSum = Math.max(maxSum,ans);
                } else {
                    i = j + 1;
                    j = i;
                    ans = 0;//和清零
                }
            }
        }
        return maxSum;
    }
*/